1399D - Binary String To Subsequences - CodeForces Solution

#include<bits/stdc++.h>
using namespace std ;
#define ll long long

int main(){
    int t ; cin>>t ; 
    while(t--){
        int n ; cin>>n ; 
        string s ; cin>>s ; 
        set<int>ones,zeros ; 
        
        for(int i=0; i<n; i++){
            if(s[i]=='1'){
                ones.insert(i) ; 
            }
            else{
                zeros.insert(i) ;
            }
        }
        
        int pre = -1 ; 
        vector<int>ans(n,0) ; 
        int ct=0 ;  
        
        while(true){
            
            if(pre==-1 && ones.empty() && zeros.empty()){
                break ; 
            }
            
            if(pre==-1){
                int ind = INT_MAX ; 
                if(!ones.empty()){
                    ind = min(ind,*ones.begin()) ; 
                }
                if(!zeros.empty()){
                    bool f=0 ; 
                    if(*zeros.begin()<ind){
                        f=1 ; 
                    }
                    ind = min(ind,*zeros.begin()) ;
                    if(f){
                        zeros.erase(zeros.begin()) ; 
                    } 
                }
                if(ind==INT_MAX) break ; 
                
                if(!ones.empty() && ind==*ones.begin()){
                    ones.erase(ones.begin()) ; 
                }
                
                pre = ind ; 
            }
            else if(s[pre]=='1'){
                if(zeros.empty()){
                    ans[pre] = ct+1 ; ct++ ; pre=-1 ; continue ; 
                }
                
                auto it = zeros.lower_bound(pre) ; 
                if(it==zeros.end()){
                    ans[pre] = ct+1 ; ct++ ; pre=-1 ; continue ; 
                }
                else{
                    ans[pre] = ct+1 ; pre = *it ; zeros.erase(it) ;
                }
            }
            else if(s[pre]=='0'){
                if(ones.empty()){
                    ans[pre] = ct+1 ; ct++ ; pre=-1 ; continue ;
                }
                
                auto it = ones.lower_bound(pre) ; 
                if(it==ones.end()){
                    ans[pre] = ct+1 ; ct++ ; pre=-1 ; continue ; 
                }
                else{
                    ans[pre] = ct+1 ; pre = *it ; ones.erase(it) ;
                }
            }
        }
        
        cout<<ct<<endl;
        for(auto x:ans){
            cout<<x<<" " ; 
        }cout<<endl;
    }
}